Conventionally, a compression technology is widespread that has its object to effectively transmit or accumulate digital images, and that compresses the amount of information of an image by motion compensation and orthogonal transform such as discrete cosine transform, for example, by using redundancy unique to the image. For example, an image encoding device and an image decoding device conforming to a standard technology such as H.26x standards developed by ITU-T or MPEG-y standards developed by MPEG (Moving Picture Experts Group) are widely used in various scenes, such as accumulation and distribution of images by a broadcaster and reception and accumulation of images by a general user.
The H.26x standards (ITU-T Q6/16 VCEG) are standards developed initially with the aim of performing encoding that is suitable for communications such as video telephones and video conferences. The H.26x standards are known to requite a large computation amount for encoding and decoding, but to be capable of realizing a higher compression ratio, compared with the MPEG-y standards. Furthermore, with Joint Model of Enhanced-Compression Video Coding, which is a part of the activities of MPEG4, a standard allowing realization of a higher compression ratio by adopting a new function while being based on the H.26x standards is developed. This standard was made an international standard under the names of H.264 and MPEG-4 Part 10 (Advanced Video Coding; AVC) in March 2003.
One important technique in the image encoding method describe above is in-screen prediction, that is, intra prediction. Intra prediction is a technique of using a correlation between adjacent blocks in an image and predicting the pixel value of a certain block from the pixel value of another block that is adjacent to thereby reduce the amount of information to be encoded. With an image encoding method before MPEG4, only the DC component and the low frequency component of an orthogonal transform coefficient were the targets of intra prediction, but with H.264/AVC, intra prediction is possible for all the pixel values. By using intra prediction, a significant increase in the compression ratio can be expected for an image where the change in the pixel value is gradual, such as an image of the blue sky, for example.
In H.264/AVC, the intra prediction can be made using a block of, for example, 4×4 pixels, 8×8 pixels, or 16×16 pixels as a processing unit (that is, a prediction unit (PU)). In HEVC (High Efficiency Video Coding) whose standardization is under way as a next-generation image encoding scheme subsequent to H.264/AVC, the size of the prediction unit is about to be extended to 32×32 pixels and 64×64 pixels (see Non-Patent Literature 1).
To make an intra prediction, the optimum prediction mode to predict a pixel value of a block to be predicted is normally selected from a plurality of prediction modes. The prediction mode is typically distinguished by the prediction direction from a reference pixel to a pixel to be predicted. In H.264/AVC, for example, when predicting a color difference component, four prediction modes of the average value prediction, horizontal prediction, vertical prediction, and plane prediction can be selected. Further, in HEVC, an additional prediction mode called a linear model (LM) mode that predicts the pixel value of a color difference component using a linear function of a dynamically built luminance component as a prediction function is proposed (see Non-Patent Literature 2).